package my.jwds.p380;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RandomizedSet {

    public static void main(String[] args) {

        RandomizedSet obj = new RandomizedSet();
        long start = System.currentTimeMillis();
        obj.insert(1);
        obj.remove(2);
        obj.insert(2);
        obj.getRandom();
        obj.remove(1);

        obj.insert(2);
        obj.getRandom();
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));

    }

    Map<Integer,Integer> valueMap;
    List<Integer> list;

    public RandomizedSet() {
        valueMap = new HashMap<>();
        list = new ArrayList<>();

    }

    public boolean insert(int val) {
        if (!valueMap.containsKey(val)){
            valueMap.put(val,list.size());
            list.add(val);
            return true;
        }
        return false;
    }

    public boolean remove(int val) {
        if (valueMap.containsKey(val)){
            int index = valueMap.get(val);
            int lastValue = list.get(list.size()-1);
            list.set(index,lastValue);
            list.remove(list.size()-1);
            valueMap.put(lastValue,index);
            valueMap.remove(val);
            return true;
        }
        return false;
    }

    public int getRandom() {
        int random = (int) (Math.random() * list.size());
        return list.get(random);
    }
}